package ab_pract;

import java.util.ArrayList;
import java.util.Collections;

public class Av2 {

	private int[][] matrix;
	private int n;

	Av2(int[][] matrix) {
		this.matrix = matrix;
		this.n = matrix.length;
	}

	public void start() {
		long ini = System.currentTimeMillis();

		System.out.println(n);

		int path = 0;
		boolean origin[] = new boolean[n];
		boolean destination[] = new boolean[n];
		int groups[]= new int[n];
		int count = 0;
		
		for(int i=0;i<n;i++) {
			origin[i] = false;
			destination[i] = false;
			groups[i] = -1;
		}
		
		ArrayList<NodesDistance> distances = new ArrayList<NodesDistance>();

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i != j) {
					NodesDistance nd = new NodesDistance(i, j, matrix[i][j]);
					distances.add(nd);
				}
			}
		}
		Collections.sort(distances);

		int i = 0;
		while (count < n && i < distances.size()) {
			NodesDistance nd = distances.get(i);
			int node1 = nd.getNode1();
			int node2 = nd.getNode2();
			int d = nd.getDistance();
			
			boolean or, de;
			int g1, g2;
			or = origin[node1];
			de = destination[node2];
			g1 = groups[node1];
			g2 = groups[node2];

			if (or || de || ((count < (n-1)) &&(g1 >= 0) && (g2 >= 0) && g1==g2)) {
				i++;
			} else {
				System.out.println(node1 + "," + node2 + "," + d);
				if (g1 < 0 && g2 < 0) {
					groups[node1] = i;
					groups[node2] = i;
				} else if (g1 >= 0 && g2  < 0) {
					groups[node2] = g1;
				} else if (g2 >= 0 && g1 < 0) {
					groups[node1] = g2;
				} else {
					for(int j=0; j<n; j++) {
						if(groups[j] == g2) {
							groups[j] = g1;
						}
					}
				}

				origin[node1] = true;
				destination[node2] = true;
				path += d;
				i++;
				
				count++;
			}
		}

		if (count < n) {
			System.out.println("Error en el algoritmo.");
			System.out.println(count);
			if (i >= distances.size()) {
				System.out.println("Se ha llegado al fin del ArrayList.");
			}
		}

		System.out.println(path);
		double time = System.currentTimeMillis() - ini;
		System.out.println("Tiempo: " + (time / 1000.0) + " segundos");

	}
}
